//
// Created by francklinson on 2021/9/1 AT 10:32.
//
//以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。
// 请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
//
//来源：力扣（LeetCode）
//链接：https://leetcode-cn.com/problems/merge-intervals
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <algorithm>
#include <functional>
#include <climits>

using namespace std;

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>> &intervals) {
        sort(intervals.begin(),intervals.end(),[](vector<int>&a,vector<int>&b){
            return a[0]<b[0];
        });
        vector<vector<int>>ans;
        // 把最初的放进去
        ans.push_back(intervals[0]);
        // 合并
        for (int i = 1; i < intervals.size(); ++i) {
            if (intervals[i][0]<=ans.back()[1]){
                // 可以合并
                ans.back()[1] = max(intervals[i][1],ans.back()[1]);
            } else{
                ans.push_back(intervals[i]);
            }
        }
        return ans;
    }
};

int main() {
    vector<vector<int>> intervals{{1,  3},
                                  {8,  10},
                                  {2,  6},
                                  {15, 18}};
    Solution solution;
    vector<vector<int>> ans = solution.merge(intervals);
    for (vector<int> &x: ans) {
        for (int &y: x) {
            cout << y << " ";
        }
        cout << endl;
    }
    return 0;
}

